package Others;

public class _807_MaxIncreasetoKeepCitySkyline {
    //hint:every gird's max increase equals the small one of vertical and horizontal skyline.
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int[] horizontalSkyline = new int[grid[0].length];
        int[] verticalSkyline = new int[grid.length];
        //get top,bottom,left,right's skyline
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (horizontalSkyline[j] < grid[i][j]) {
                    horizontalSkyline[j] = grid[i][j];
                }
                if (verticalSkyline[i] < grid[i][j]) {
                    verticalSkyline[i] = grid[i][j];
                }
            }
        }
        int sum = 0;
        //calculate every grid's increase
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                int tempSkyline = Math.min(horizontalSkyline[j], verticalSkyline[i]);
                sum += (tempSkyline - grid[i][j]);
            }
        }
        return sum;
    }
}
